﻿#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<vector>
#include<stack>
using namespace std;
string removeDuplicates(string s) {
	string ret;
	for (int i = 0; i < s.size(); i++)
	{
		if (!ret.empty() && ret.back() == s[i])
			ret.pop_back();
		else
			ret.push_back(s[i]);
	}
	return ret;
}
bool backspaceCompare(string s, string t) 
{
	string tmp1;
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == '#')
		{
			if (!tmp1.empty())
				tmp1.pop_back();
		}
		else
			tmp1.push_back(s[i]);
	}
	string tmp2;
	for (int i = 0; i < t.size(); i++)
	{
		if (s[i] == '#')
		{
			if (!tmp2.empty())
				tmp2.pop_back();
		}
		else
			tmp2.push_back(t[i]);
	}
	return tmp1 == tmp2;
}
int calculate(string s) {
	vector<int> st;
	char op = '+';
	int i = 0,n=s.size();
	while(i<n)
	{
		if (s[i] >= '0' && s[i] <= '9')
		{
			// 先把这个数字给提取出来
			int tmp = 0;
			while (i < n && s[i] >= '0' && s[i] <= '9')
			{
				tmp = tmp * 10 + s[i] - '0';
				i++;
			}
			if (op == '+')
				st.push_back(tmp);
			else if (op == '-')
				st.push_back(-tmp);
			else if (op == '*')
				st.back() *= tmp;
			else if (op == '/')
				st.back() /= tmp;
		}
		else if (s[i] == ' ')
			i++;
		else
			op = s[i++];
	}
	int ret = 0;
	for (auto& e : st)
		ret += e;
	return ret;
}
string decodeString(string s) {
	stack<int> nums;
	stack<string> st;
	st.push("");
	int i = 0, n = s.size(); 
	while (i < n)
	{
		if (s[i] >= '0' && s[i] <= '9')
		{
			int tmp = 0; while (s[i] >= '0' && s[i] <= '9') 
			{
					tmp = tmp * 10 + (s[i] - '0'); i++;
			}
			nums.push(tmp);
		}
		else if (s[i] == '[') 
		{
			i++; // 把括号后⾯的字符串提取出来 
			string tmp = "";
			while(s[i] >= 'a' && s[i] <= 'z')
			{ 
				tmp += s[i];
				i++;
			}
			st.push(tmp);
		}
		else if(s[i] == ']') 
		{ 
			string tmp = st.top();
			st.pop(); 
			int k = nums.top(); 
			nums.pop(); 
			while(k--) 
			{ 
				st.top() += tmp;
			}
			i++; // 跳过这个右括号
		}
		else 
		{ 
			string tmp;
			while(i < n && s[i] >= 'a' && s[i] <= 'z') 
			{ 
				tmp += s[i];
				i++; 
			}
			st.top() += tmp; 
		} 
	}
	return st.top();
}
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) 
{
	stack<int> st;
	int i = 0;
	for (auto& e : pushed)
	{
		st.push(e);
		while(popped[i] == st.top())
		{
			st.pop();
			i++;
		}
	}
	return st.empty();
}
int main()
{

	return 0;
}